package com.algorithm.heap;/*
 *@Author:DOWN
 *@Date:2022/2/21 15:33
 *@Comment:最大堆
 */

import com.algorithm.arrays.Arrays;

public class MaxHeap<E extends Comparable<E>> {
    //自封装-动态数组
    private Arrays<E> data;


    /**
     * 可接受传入的容量
     *
     * @param capacity 容量
     */
    public MaxHeap(int capacity) {
        data = new Arrays<>(capacity);
    }


    /**
     * 默认容量
     */
    public MaxHeap() {
        data = new Arrays<>();
    }


    /**
     * 直接传入数组
     *
     * @param arrs 泛型数组
     */
    public MaxHeap(E[] arrs) {
        data = new Arrays<>(arrs);
        for (int i = parentIndex(arrs.length - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 获取长度
     *
     * @return int
     */
    public int getSize() {
        return data.getSize();
    }

    /**
     * 是否为空
     *
     * @return boolean
     */
    public boolean isEmpty() {
        return data.isEmpty();
    }

    /**
     * 获取上几节点的 索引
     *
     * @param index 元素索引
     * @return int
     */
    private int parentIndex(int index) {
        if (index == 0) {
            throw new IllegalArgumentException(" This index is out of size");
        }
        return (index - 1) / 2;
    }

    /**
     * 获取左节点的索引
     *
     * @param index 元素索引
     * @return int
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 获取右节点的索引
     *
     * @param index 元素索引
     * @return int
     */
    private int rightChild(int index) {
        return index * 2 + 2;
    }

    /**
     * 添加新的元素
     *
     * @param e 泛型
     */
    public void add(E e) {
        data.add(e);
        siftUp(getSize() - 1);
    }

    /**
     * 元素上浮-至正确位置
     *
     * @param index 元素索引
     */
    private void siftUp(int index) {
        while (index > 0 && data.get(index).compareTo(data.get(parentIndex(index))) > 0) {
            data.swap(index, parentIndex(index));
        }
    }

    /**
     * 获取最大元素
     *
     * @return 泛型
     */
    public E findMax() {
        if (data == null || getSize() == 0) {
            throw new IllegalArgumentException("Can not find Max item");
        }
        return data.get(0);
    }

    /**
     * 取出最大元素，重新调整位置
     *
     * @return 泛型
     */
    public E extractMax() {
        E ret = findMax();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    /**
     * 元素下沉-至正确位置
     *
     * @param index 元素索引
     */
    private void siftDown(int index) {
        while (leftChild(index) < getSize()) {
            int j = leftChild(index);
            if (j + 1 < getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j++;
            }
            if (data.get(index).compareTo(data.get(j)) >= 0) {
                break;
            }
            data.swap(index, j);
            index = j;
        }
    }

    /**
     * 取出最大元素->加入新的元素->重新调整位置
     *
     * @param e 元素
     * @return 泛型
     */
    public E replaceByMax(E e) {
        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }
}
